package zuoshen_video;
import java.util.*;


public class GreedyProblems {
    class HuffmanProblem {
        //基础哈夫曼问题
        public int huffman(int[] nums) {
            Queue<Integer> queue = new PriorityQueue<>((n1, n2) -> n1 - n2);
            for (int i = 0; i < nums.length; i++) {
                queue.offer(nums[i]);
            }
            Queue<Integer> res = new LinkedList<>();
            int n1, n2, sum;
            while (queue.size() > 1) {
                n1 = queue.poll();
                n2 = queue.poll();
                sum = n1 + n2;
                res.add(sum);
                queue.offer(sum);
            }
    
            sum = 0;
            while (!res.isEmpty()) {
                sum += res.poll();
            }
            return sum;
        }

        //项目最大收益问题
        public long maxProjectProfit() {
            Scanner scanner = new Scanner(System.in);
            String s = scanner.nextLine();
            String[] ss = s.split(" ");
            int n = Integer.parseInt(ss[0]), //项目最大数量
            w = Integer.parseInt(ss[1]), //项目启动资金
            k = Integer.parseInt(ss[2]); //最多可以做的项目数量
            s = scanner.nextLine();
            ss = s.split(" ");
            int[] costs = Arrays.stream(ss).mapToInt(Integer::parseInt).toArray(); //项目花费
            s = scanner.nextLine();
            ss = s.split(" ");
            int[] profits = Arrays.stream(ss).mapToInt(Integer::parseInt).toArray();//项目收益

            //根据题设决定顺序，进而选择最大收益的进行方式
            Node[] projects = new Node[n];
            for (int i = 0; i < n; i++) {
                projects[i] = new Node(costs[i], profits[i]);
            }
            scanner.close();
            long weight = (long)w;
            return maxProfit(n, weight, k, projects);
        }

        class Node {
            public int cost;
            public int profit;
            public Node(int cost, int profit) {
                this.cost = cost;
                this.profit = profit;
            }
        }

        public long maxProfit(int n, long w, int k, Node[] projects) {
            //按照花销升序进行小根堆
            Queue<Node> costQueue = new PriorityQueue<>((n1, n2) -> n1.cost - n2.cost);
            //按照收益降序建立大根堆
            Queue<Node> profitQueue = new PriorityQueue<>((n1, n2) -> n2.profit - n1.profit);

            //将所有节点全部放入花销根堆，保证能够足够花销
            for (int i = 0; i < n; i++) {
                costQueue.offer(projects[i]);
            }

            int count = 0;  //count记录当前做完的项目数量
            
            //从花销根堆中获得当前可以满足的花销的项目，放入收益根堆，从中谋取最大收益
            while (count < k) {
                while (!costQueue.isEmpty() && costQueue.peek().cost < w) {
                    profitQueue.offer(costQueue.poll());
                }
                //拿出收益最大的项目完成
                Node t = profitQueue.poll();
                w += t.profit; //当前项目资金增加，可以解锁更多项目
                count++;
            }

            return w;
        }
    }

    static class MeetingRoom {
        public static void main(String[] args) {
            Scanner s = new Scanner(System.in);
            int n = Integer.parseInt(s.nextLine());
            // int n = 3;
            int[] start = new int[n], end = new int[n];
            // for (int i = 0; i < n; i++) {
            //     int[] num = Arrays.stream(s.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            //     start[i] = num[0];
            //     end[i] = num[1];
            // }
            String str = "4 16 18 20 14 21 20 23 10 22 1 10 2 14 3 16 20 23 4 7 18 23 6 21 12 13 4 22 12 13 20 23 13 18 10 19 11 23 8 9  13 22 17 23 12 22 16 19 15 21 4 10 2 4 16 19 15 17 21 23 17 20 14 19 14 20 9 22 11 18 16 18 21 22 20 23 9 10 14 20 16 17 15 21";
            String[] ss = str.split(" ");
            start = new int[]{1, 11, 10};
            end = new int[]{10, 20, 11};
            int len = ss.length / 2;
            start = new int[len];
            end = new int[len];
            for (int i = 0; i < len * 2; i++) {
                start[i] = Integer.parseInt(ss[i]);
                end[i] = Integer.parseInt(ss[++i]);
            }
            s.close();
            System.out.println(numberOfMettingRooms(start, end));
        }

        static class Node {
            public int start;
            public int end;
            public Node(int start, int end) {
                this.start = start;
                this.end = end;
            }
        }
        public static int numberOfMettingRooms(int[] start, int[] end) {
            int n = start.length;
            Node[] nodes = new Node[n];
            for (int i = 0; i < n; i++) {
                nodes[i] = new Node(start[i], end[i]);
            }
            Queue<Node> queue = new PriorityQueue<>((n1, n2) -> n1.end - n2.end); 
            for (int i = 0; i < n; i++) {
                queue.offer(nodes[i]);
            }
            Node last = queue.poll(), cur;
            int count = 1, res = 1;
            while (queue.size() > 0) {
                cur = queue.poll();
                if (cur.start < last.end) {
                    count = 1; //新开了一个会议室，重新计数
                } else {
                    //可以复用这个会议室，
                    count++;
                }
                res = Math.max(count, res);
            }
            return res;
        }

    }
}


/* 

4 3 2
5 4 1 2
3 5 3 2
*/
